Processors often use a cache to improve performance and decrease system costs. Caches temporarily store recently accessed information (blocks of instructions or data) in a small memory that is faster to access than a larger main memory. Caches are effective because a block that has been accessed once is likely to be accessed soon again or is often near a recently accessed block. Thus, as a task executes, the working set of a task (the instructions and data currently required for the task) is stored in the cache in the event that the information may be accessed again. A cache typically maps multiple blocks of information from the main memory into one place in a cache, typically referred to as a “set.” A “block” refers to the minimum unit of information that can be present in a cache and a “frame” is the place in a cache where a single block may be stored. In a set associative cache, multiple frames are grouped into sets. For example, a two-way set associative cache has two frames in each set.
In many embedded applications, a primary task may be interrupted by one or more secondary tasks. Thus, following an interruption, as a secondary, interrupting task executes, the working set of the interrupting task is stored in the cache, potentially evicting the working set of the primary, interrupted task and thereby decreasing the performance of the primary, interrupted task when it resumes execution. When the primary, interrupted task resumes execution, portions of the working set that have been evicted from the cache must be obtained from main memory, causing “cache misses.” Thus, the execution time of the primary, interrupted task is extended by the time taken to run the secondary task plus the miss penalty due to obtaining evicted portions of the cached information from the main memory.
A critical parameter of a real-time task is its maximum response time over all possible inputs. In some systems, a task scheduler allocates a processor's cycles among multiple tasks to meet their response time requirements. Thus, the worst-case execution time of each task must be known. When instruction timings or execution paths are uncertain, conservative (worst case) assumptions are often made that may waste system capability or lead to an unnecessarily costly system. If the resulting worst-case time-bound is loose, a task is allocated more execution time than it can possibly use, wasting system capability and performance. Efficient system design thus requires methods to tightly estimate the effect of complex cache behavior. A need therefore exists for methods and apparatus that evaluate the additional execution time of the primary, interrupted task attributed to any interrupts. A further need exists for methods and apparatus that establish a bound on the effect of task interference in an instruction cache shared by multiple tasks.